#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}

};

class Solution1 {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int cur = 0, mn = 0, ans = 0;
        for (int i = 0; i < n; ++i)
        {
            cur += gas[i] - cost[i];
            if (cur < mn)
            {
                mn = cur;
                ans = i + 1;
            }
        }
        return cur < 0 ? -1 : ans;
    }
};

class Solution2 {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n, 1);
        for (int i = 1; i < n; ++i)
            if (ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;

        int res = left[n - 1]; int right = 1;
        for (int i = n - 2; i >= 0; --i)
        {
            if (ratings[i] > ratings[i + 1])
                right++;
            else
                right = 1;
            res += max(left[i], right);
        }
        return res;
    }
};

class LRUCache {
private:
    struct Node
    {
    public:
        int key, val;
        Node* prev, * next;
        Node(int key = 0, int val = 0) : key(key), val(val) {}
    };

    Node dummy;
    int capacity;
    unordered_map<int, Node*> mp;
private:
    void remove(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void insert(Node* node)
    {
        node->prev = &dummy;
        node->next = dummy.next;

        dummy.next->prev = node;
        dummy.next = node;
    }

    Node* getnode(int key)
    {
        auto it = mp.find(key);
        if (it == mp.end())
            return nullptr;
        remove(it->second);
        insert(it->second);
        return it->second;
    }
public:
    LRUCache(int capacity) : capacity(capacity)
    {
        dummy.prev = &dummy;
        dummy.next = &dummy;
    }

    int get(int key) {
        Node* ret = getnode(key);
        if (ret == nullptr) return -1;
        return ret->val;
    }

    void put(int key, int value) {
        Node* ret = getnode(key);
        if (ret != nullptr)
        {
            ret->val = value;
            return;
        }
        Node* newnode = new Node(key, value);
        insert(newnode);
        mp[key] = newnode;
        if (mp.size() > capacity)
        {
            Node* old = dummy.prev;
            remove(old);
            mp.erase(old->key);
            delete old;
        }
    }
};